#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

struct ListNode 
{
    int val;
    struct ListNode* next;
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* cura = headA;
    struct ListNode* curb = headB;
    int a = 0;
    int b = 0;
    while (cura->next)
    {
        cura = cura->next;
        a++;
    }
    while (curb->next)
    {
        curb = curb->next;
        b++;
    }
    if (cura != curb)
    {
        return NULL;
    }
    int mid = abs(a - b);
    struct ListNode* leng = headA;
    struct ListNode* sort = headB;
    if (b > a)
    {
        leng = headB;
        sort = headA;
    }
    while (mid--)
    {
        leng = leng->next;
    }
    while (leng != sort)
    {
        leng = leng->next;
        sort = sort->next;
    }
    return sort;
}

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            struct ListNode* newhead = meet->next;
            meet->next = NULL;
            return getIntersectionNode(head, newhead);
        }
    }
    return NULL;
}